package com.arron.algorithm.leetcodetop100.技巧.原地hash;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * leetcode 448. 找到所有数组中消失的数字
 *
 */
public class 找到所有数组中消失的数字 {


    public static void main(String[] args) {

        int[] a = {4,3,2,7,8,2,3,1};
        // 4+8 = 12 7+8=15 14%8
        findDisappearedNumbers(a);
        print(a);

    }

    //1 ·使用Hashset 预存1...n数
    public static List<Integer> findDisappearedNumbers01(int[] array){

        Set<Integer> set = new HashSet<>();

        for (int i = 1; i <= array.length; i++) {
                set.add(i);
        }
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < array.length; i++) {
            if (!set.contains(array[i])){
                res.add(array[i]);
            }

        }

        return res;
    }

        //2. 数组的原地hash
        public static List<Integer> findDisappearedNumbers(int[] array){

            for (int i = 0; i < array.length; i++) {

                //防止已经累加过的数计算出来的下标越界，
                int index = (array[i] -1) % array.length;

                array[index] = array[index] + array.length;
            }
            List res = new ArrayList<Integer>();
            for (int i = 0; i < array.length; i++) {

                if (array[i]<array.length){
                    res.add(i+1);
                }
            }
            return res;
        }


    public static void print(int[] array){
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }




}
